package offer.day16;

public class No25mergeList {
    /*
     * 面试题25：合并两个排序的链表
     * 题目：输入两个递增序列的链表，合并这两个链表并是新链表中的节点仍然是递增排序的。
     * 例如： 输入链表1:1->3->5->7和链表2:2->4->6->8,
     * 将二者合并之后的升序链表为：1->2->3->4->5->6->7->8
     *
     *
     * 思路：取两个链表的头节点，比较大小，小的作为新的合并的链表的头节点；
     *            然后将剩余的两个链表的头节点在进行比较，小的再作为新的合并的链表的下一个节点，
     *            。。。。。。直到两个链表都到末尾为止。若是一个先到达末尾，则另一个直接将剩余数据连接到新的链表之后即可。
     *           还要注意空指针问题：若是开始一个链表为空，则合并的新链表就是另一个有数据的链表。
     *           	       若是两个都为空链表，则新链表为空链表。
     *
     *   这是一个递归的过程
     *   递归就是不断直接或间接调用自己的函数；
     *   迭代是不断执行函数中一部分代码的过程。
     * */
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);
        ListNode seven = new ListNode(7);
        head.next = three;
        second.next = four;
        three.next = five;
        four.next = six;
        five.next = seven;
        six.next = null;
        seven.next = null;
        showNode(head);
        showNode(second);

        showNode(mergeList(head,second));
    }

    public static ListNode mergeList(ListNode head1,ListNode head2){
        ListNode newHead=null;
        if(head1==null) return head2;
        if(head2==null) return head1;
        if(head1.data<head2.data){
            newHead=head1;
            newHead.next=mergeList(head1.next,head2);
        }else{
            newHead=head2;
            newHead.next=mergeList(head1,head2.next);
        }
        return newHead;
    }

    public static void showNode(ListNode head){
        ListNode tmp=head;
        while(tmp!=null){
            System.out.println(tmp);
            tmp=tmp.next;
        }
        System.out.println();
    }
}
